package DataStructrue.dp;

public class DigitDP {
    private char[] s;//n的每个数位
    private int[] dp;//初始值为-1,存储递归函数的值,每个函数为1个状态,其中每个数位任意取值

    /**
     *
     * @param i 当前数位索引
     * @param path 路径变量
     * @param lim 当前数位是否受到限制
     * @param fill 之前数位是否已经填入数字
     * @return
     */
    public int f(int i, int path,boolean lim,boolean fill) {
        //边界条件
        if (i == s.length) {
            System.out.println(path);
            return fill?1:0;//0不进入计数
        }
        //一个状态中每个数位可以取任意值,所以需要无限制且已填过数
        if (!lim && fill && dp[i] != -1) return dp[i];
        int res = 0;
        if(!fill)//之前不填,当前位也可选择不填,如果已填,则当前位必须填
            res+=f(i+1,path,false,false);
        int up = lim ? s[i] - '0' : 9;//如果没有限制,最大为9,否则为n对应位的数字
        //如果之前已填,从0开始,否则从1开始
        for (int d = fill?0:1; d <= up; d++) {
            res += f(i + 1, path*10+d,lim && d == up,true);//当前位有限制且为最大值时,下一位需要限制
        }
        //当前状态应为任意取值
        if (!lim && fill) dp[i] = res;
        return res;
    }







}
